package com.wkh.test;

import org.junit.Test;

import java.util.Arrays;

public class BinarySearchDemo {
    @Test
    public void basicBinarySearchDemo1(){
        int[] a = {2,3,8,20,43};
        int target = 5;
        int result = basicBinarySearch(target, a);
        System.out.println(result);



        if (result < 0){
            //插入点insertPoint
            int insertPoint = -(result+1);
            System.out.println(insertPoint);
            int[] b = new int[a.length+1];
            //扩容
            System.arraycopy(a,0,b,0,insertPoint);
            b[insertPoint] = target;
            System.arraycopy(a,insertPoint,b,insertPoint+1,a.length-insertPoint);
            System.out.println(Arrays.toString(b));
        }
    }

    @Test
    public void basicBinarySearchLeftMostDemo1(){
        int[] a = {2,3,8,8,8,8,8,20,43};
        int target = 8;
        int result = basicBinarySearchLeftMost1(target, a);
        System.out.println(result);
    }

    @Test
    public void basicBinarySearchRightMostDemo1(){
        int[] a = {2,3,8,8,8,8,8,20,43};
        int target = 8;
        int result = basicBinarySearchRightMost1(target, a);
        System.out.println(result);
    }
    @Test
    public void balancedSearchDemo(){
        int[] a = {2,3,8,20,43};
        int target = 8;
        int i = balancedSearch(target, a);
        System.out.println(i);
    }

    public int basicBinarySearch(int target , int[] arr){
        int high = arr.length - 1;
        int low = 0;
        while (low<=high){
            int mid = (low + high) >>> 1;
            if (arr[mid] > target){
                high = mid-1;
            }else if (arr[mid] < target){
                low = mid+1;
            }else{
                return mid;
            }
        }
        return -(low+1);
    }
    //查找最左边的重复元素的索引
    public int basicBinarySearchLeftMost1(int target , int[] arr){
        int high = arr.length - 1;
        int low = 0;
        //记录最左端的索引
        int candidate = -1;
        while (low<=high){
            int mid = (low + high) >>> 1;
            if (arr[mid] > target){
                high = mid-1;
            }else if (arr[mid] < target){
                low = mid+1;
            }else{
                candidate = mid;
                high = mid - 1;
            }
        }
        return candidate;
    }

    //查找最右边的重复元素的索引
    public int basicBinarySearchRightMost1(int target , int[] arr){
        int high = arr.length - 1;
        int low = 0;
        //记录最左端的索引
        int candidate = -1;
        while (low<=high){
            int mid = (low + high) >>> 1;
            if (arr[mid] > target){
                high = mid-1;
            }else if (arr[mid] < target){
                low = mid+1;
            }else{
                candidate = mid;
                low = mid + 1;
            }
        }
        return candidate;
    }

    //平衡二分查找
    public int balancedSearch(int target , int[] arr){
        int low = 0;
        int high = arr.length;
        while (low+1 < high){
            int mid = (low + high) >>> 1;
            if (target < arr[mid]){
                high = mid;
            }else{
                low = mid;
            }
        }
        return (arr[low] == target) ? low : -1;
    }
}
